//在线操作与离线操作 - 采花

#include <iostream>
#include <algorithm>
using namespace std;
#define lowbit(x) (x & -x)
const int N = 2e6 + 10;
int a[N], s[N];
int n, c, m;
int last[N], llast[N];
int ret[N];

struct node
{
    int l, r, id;
}q[N];

void modify(int x, int k)
{
    for(int i = x; i <= n; i += lowbit(i))
        s[i] += k;
}

int query(int x)
{
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)) sum += s[i];
    return sum;
}

bool cmp(node& x, node& y)
{
    return x.r < y.r;
}

int main()
{
    cin >> n >> c >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }

    sort(q + 1, q + 1 + m, cmp);
    
    int pos = 0;
    for(int i = 1; i <= m; i++)
    {
        int l = q[i].l, r = q[i].r, id = q[i].id;
        while(pos <= r)
        {
            int x = a[i];
            if(!last[x]) last[x] = pos;
            else if(!llast[x])
            {
                modify(last[x], 1);
                llast[x] = last[x];
                last[x] = pos;
            }
            else
            {
                modify(llast[x], -1);
                modify(last[x], 1);
                llast[x] = last[x];
                last[x] = pos;
            }
            pos++;
        }
        ret[id] = query(r) - query(l - 1); 
    }
    for(int i = 1; i <= m; i++) cout << ret[i] << endl;
    return 0;
}